Corelab Seminar
2021-2022
Aris Filos-Ratsikas
On the Complexity of Consensus-Halving and Necklace Splitting
Abstract.
The Necklace Splitting problem and its continuous counterpart, the Consensus-Halving problem, are classic problems in combinatorics, with applications to fair division and social choice theory. A distinctive characteristic of these problems is that they are total, i.e., they always have a solution, but it was not known until recently whether such a solution can be found efficiently. In this talk, I will present results from a series of recent papers (from 2018 to 2021) related to the computational complexity of these problems. The talk will also provide a gentle introduction to the computational subclasses of the class TFNP, the class of total search problems for which a solution can be verified in polynomial time.